
from typing import Dict


_NO_RECORD = object()


def memoize(func):
    def memo_wrapper(self, *args):
        memo: Dict[int, Dict] = self._memo
        pos = self._pos()

        key = func, args
        single_memo = memo.get(pos)

        if single_memo is None:
            memo[pos] = single_memo = {}

        res, end_pos = single_memo.get(key, (_NO_RECORD, -1))

        if res is not _NO_RECORD:
            self._reset(end_pos)
        else:
            res = func(self, *args)
            new_end_pos = self._pos()
            
            if res:
                assert new_end_pos > end_pos, 'new_end_pos <= end_pos'

            single_memo[key] = res, new_end_pos

        return res
    return memo_wrapper


def memoize_for_left_recursion(func):
    def memo_wrapper(self, *args):
        memo: Dict[int, Dict] = self._memo
        pos = self._pos()

        key = func, args
        single_memo = memo.get(pos)

        if single_memo is None:
            memo[pos] = single_memo = {}

        res, end_pos = single_memo.get(key, (_NO_RECORD, -1))

        if res is not _NO_RECORD:
            self._reset(end_pos)
        else:
            single_memo[key] = None, pos
            old_res, old_pos = None, pos
            # first call return None to 'control' recursion

            while True:
                self._reset(pos)
                res = func(self, *args)
                new_end_pos = self._pos()
                if old_pos >= new_end_pos:
                    break
                single_memo[key] = old_res, old_pos = res, new_end_pos

            res = old_res
            self._reset(old_pos)

        return res
    return memo_wrapper
